class MazeGrid:
    """A grid representing a maze.

    Conform to the specification, version 6, at <http://goo.gl/dMRovy>.
    """

    def __init__(self, x_size, y_size):
        self.sizeX = x_size
        self.sizeY = y_size
        self._maze_list = 0

        self.entrance = None
        self.exits = set()

    def is_coordinate(self, x, y):
        """Return true if the given coordinate is valid."""

        return (
            0 <= x < self.sizeX and 0 <= y < self.sizeY
            and x == int(x) and y == int(y)
        )

    def set_entrance(self, x, y):
        assert self.is_coordinate(x, y)
        if not self[x, y]:
            # entrance only makes sense if passable
            raise ValueError("Can't put entrance on impassible square.")

        self.entrance = x, y

    def add_exit(self, x, y):
        assert self.is_coordinate(x, y)
        if not self[x, y]:
            # exit only makes sense if passable
            raise ValueError("Can't put exit on impassible square.")

        self.exits.add((x, y))

    def details(self):
        """Yield all maze details; useful for drawing."""

        # Entrance
        if self.entrance is not None:
            yield {
                "type": "entrance",
                "location": self.entrance
            }

        # Exits
        for ext in self.exits:
            yield {
                "type": "exit",
                "location": ext
            }

    # Set a value
    def set(self, x, y, value):
        value = int(value)
        if value < 0 or value > 1:
            raise ValueError('only 0 (impassible) or 1 (passable) accepted')
        elif value == 0 and ((x, y) in self.exits or (x, y) == self.entrance):
            raise ValueError('cannot set a entrance or exit impassible')
        elif value != self[x, y]:
            self._maze_list ^= 1 * 1 << (x * self.sizeY + y)

    # Set a 2D cuboid region with a value (Can also set a line, or a single value)
    def setRegion(self, x1, y1, x2, y2, value):
        x1, y1, x2, y2 = abs(x1), abs(y1), abs(x2), abs(y2)
        for y in range(min(y1, y2), max(y1, y2) + 1):
            for x in range(min(x1, x2), max(x1, x2) + 1):
                self.set(x, y, value)

    # Get a value
    def get(self, x, y):
        return self._maze_list >> (x * self.sizeY + y) & 1

    def get_neighbours(self, x, y):
        if self.is_coordinate(x, y - 1) and self.get(x, y - 1):
            yield x, y - 1
        if self.is_coordinate(x, y + 1) and self.get(x, y + 1):
            yield x, y + 1
        if self.is_coordinate(x - 1, y) and self.get(x - 1, y):
            yield x - 1, y
        if self.is_coordinate(x + 1, y) and self.get(x + 1, y):
            yield x + 1, y

    # Returns a human-readable version of the Map
    def __str__(self):
        s = ['   ']

        # Key (x-coordinates)
        for i in range(self.sizeX):
            s.append('{:2}'.format(i))
        s.append('\n')

        for y in range(self.sizeY):
            # Key (y-coordinates)
            s.append('{:2} '.format(y))

            # Maze itself
            for x in range(self.sizeX):
                s.append(str('  ' if self._maze_list[x][y] == 1 else '##'))
            s.append("\n")

        s.append("-" * (self.sizeX * 2 + 3) + "\n")
        # Add details.
        for det in self.details():
            s.append("{} at {}".format(det['type'], det['location']) + '\n')
        return "".join(s)

    # Convenience method for accessing maze.
    # just use `maze[x, y]`
    def __getitem__(self, coord):
        if len(coord) != 2:
            raise KeyError('maze access only with maze[x, y]')
        return self.get(coord[0], coord[1])

    def __setitem__(self, coord, val):
        if len(coord) != 2:
            raise KeyError('maze access only with maze[x, y]')
        self.set(coord[0], coord[1], val)

# Usage demo
if __name__ == "__main__":
    maze = MazeGrid(21, 21, 0)
    maze.setRegion(1, 1, 19, 19, 1)
    maze[0, 1] = 1
    maze.set(0, 10, 1)
    maze.set(20, 10, 1)
    maze.set_entrance(0, 1)
    maze.add_exit(19, 19)
    print(maze)

    input()
